package com.data.bobostructure.chapter2;

import com.data.bobostructure.utils.SortUtils;

import java.util.Arrays;

/**
 * Created by wangbing on 2018/3/26.
 */
public class MergeSortion02 {
    private MergeSortion02() {
    }

    //    将arr[l,mid]和merge
    private static  void merge(Comparable arr[],int l,int mid,int r){
//        临时空间的生成
        Comparable[] aux = Arrays.copyOfRange(arr,l,r+1);
        for (int i=l;i<=r;i++){
            aux[i-l]= arr[i];
        }

        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l;
        int j = mid+1;



        for (int k = l;k<=r;k++){
            /**
             * 数组越界问题:
             * 当归并开始时，如果有一方率先完成了排序，那么另一方就按照顺序，往剩余位置填充即可
              */
//        右边排好序了

            if (i>mid){
                arr[k] = aux[j-l];
                j++;
            }

            else if (j>r){
                arr[k] = aux[i-l];
                i++;
            }
// 常规操作
            // 左半部分所指元素 < 右半部分所指元素
            else if (aux[i-l].compareTo(aux[j-l])<0){
                arr[k] = arr[i+1];
                i++;

            }else {
                // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = arr[j-1];
                j++;
            }
        }



    }
    // 递归使用归并排序,对arr[l...r]的范围进行排序
    private  static void mergeSort(Comparable arr[], int l, int r){

        /**
         * 优化2： 当这里的l和r越来越接近，就近乎有序；
         * 因为近乎有序的数组排序，适合插入排序！
         */
//        if (l>=r){
//            return ;
//        }
        if (r-l<=15){
            insertSortOption(arr,l,r);
            /**
             * todo
             * 记得return，函数返回出口，否则会出现溢出
             */
            return;
        }
        int mid = (l+r)/2;
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);
        /**
         * 优化1：从下往上看，如果第mid个元素小于mid+1个元素，那么这个arr就是有序的，不需要在排序
         */

        if (arr[mid].compareTo(arr[mid+1])>0){
            merge(arr, l, mid, r);
        }


    }

    private static void insertSortOption(Comparable[] arr, int l, int r) {
        if (l>r){
            return;
        }
        for (int i=l+1;i<r;i++){
            Comparable temp = arr[i];
            int j;
//            插入到有序数组的合适位置
            for (j=i;j>l;j--){
                if (arr[j].compareTo(temp)>0){
                    arr[j] = arr[j-1];
                }


            }
            arr[j]=temp;
        }
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;
        mergeSort(arr, 0, n-1);
    }
    public static void main(String[] args) {
        int N = 1000000;
        Integer[] arr = SortUtils.generateRandomArray(N, 0, 100000);
//        long start = System.currentTimeMillis();
//        sort(arr);
//        System.out.println("花费时间："+(System.currentTimeMillis()-start));
        SortUtils.testSort("com.data.structure.chapter2.MergeSortion01","sort", arr);
        SortUtils.testSort("com.data.structure.chapter2.MergeSortion02","sort", arr);
//        SortUtils.testSort("com.data.structure.chapter1.SelectionSort03","sort", arr);

        return;
    }
    /**
     * 有一件很奇怪的事情：
     * 当我在 70行r-l<=15)写成r-l>=15的时候，运算变得奇慢无比，也就是在数组元素很多的时候用插入排序；在数组元素少的时候用归并排序
     * 但是直接用插入排序，速度却很快。。。。。。。。。。。
     */

}
